// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 * Creator: yanking
 * Create time: 2022-02-21 17:08
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.leetCode.MyLinkedList;

class MyLinkedList {

    private node head; // 定义链表头结点
    private int length; // 记录当前链表的长度

    public MyLinkedList() {
        head = new node();// 初始化链表头结点
    }

    public int get(int index) {
        // 如果索引有效则返回链表中第index个节点的值，否则返回-1
        if (index < length) {
            node p = head;
            int k = -1;
            while (k < index) {
                p = p.next;
                ++k;
            }
            return p.val;
        } else {
            return -1;
        }
    }


    public node getNode(int index) {
        // 如果索引有效则返回链表中第index个节点的值，否则返回-1
        if (index == -1) {
            return head;
        }
        if (index < length) {
            node p = head;
            int k = -1;
            while (k < index) {
                p = p.next;
                ++k;
            }
            return p;
        } else {
            return null;
        }
    }

    public void addAtHead(int val) {
        node node = new node();
        node.val = val;
        node.next = head.next;
        head.next = node;
        ++length;
    }

    public void addAtTail(int val) {
        node node = new node(val);
        // 找到尾结点
        if (length > 0) {
            node tail = getNode(length - 1);
            node.next = tail.next;
            tail.next = node;
        } else {
            node.next = head.next;
            head.next = node;
        }

        ++length;
    }

    public void addAtIndex(int index, int val) {
        // 在链表的index个元素之前添加节点
        node node = new node(val);
        if (index < -1) {
            addAtHead(val);
        } else if (index <= length) {
            node p = head;
            int k = 0;
            while (k < index) {
                p = p.next;
                ++k;
            }
            node.next = p.next;
            p.next = node;
            ++length;
        }
    }

    public void deleteAtIndex(int index) {
        if (index < length) {
            // 索引有效
            node node = getNode(index - 1);
            node.next = node.next.next;
            --length;
        }
    }

    // 使用内部类定义链表节点
    public class node {
        public int val;
        public node next;

        public node() {
        }

        public node(int val) {
            this.val = val;
        }
    }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */